1. Field of the Invention
The present invention relates to a technique of effecting conversion processing of two-dimensional data. More particularly, it relates to a data conversion processing circuit which, using the Hough transform, effects processing for data conversion which projects two-dimensional data on a plurality of straight lines with different inclinations.
2. Description of the Related Art
The Hough transform is a technique for extracting a figure such as a straight line and circle from an image, and is effective in detecting a straight line as described later. Moreover, when the Hough transform is used to carry out pattern matching, the number of arithmetic operations can be reduced. From this viewpoint, the Hough transform is thought to be applicable to motion detection of an animated image or graphic recognition. The Hough transform is actually adopted as a pre-process for processing visual information, and is thought to help to reduce the number of subsequent arithmetic operations or to help to facilitate learning processes in a neural network. Accordingly, if the Hough transform can be easily carried out, information processing that requires a large number of arithmetic operations according to the existing methods, such as compression of moving image data and graphic recognition, can be achieved relatively easily. In view of this, there is an increasing demand for an art of carrying out the Hough transform with the number of arithmetic operations being as small as possible.
To begin with, the Hough transform will be described briefly with reference to FIGS. 1a and 1b. As shown in FIG. 1a, assuming that an angle, formed by a perpendicular extending from an origin to a straight line L in the system of x and y coordinates and the x axis, is xcex8, and the length of the perpendicular is xcfx81, the straight line L is expressed as xxc2x7cos xcex8+yxc2x7sin xcex8=xcfx81. When the line L passes through a point (u, V), an equality of uxc2x7cos xcex8+vxc2x7sin xcex8=xcfx81 is established. When a trajectory (xcex8, xcfx81) where the angle xcex8 and length xcfx81 satisfy the equality is drawn in a xcfx81-xcex8 space, a sine curve shown in FIG. 1b is produced. Likewise, when a trajectory (sine curve) linking points (uxe2x80x2, vxe2x80x2) is drawn, a point of intersection between the two trajectories shall be a point (xcex80, xcfx810) In this case, xxc2x7cos xcex80+yxc2x7sin xcex80=xcfx810 expresses a straight line passing through two points (u, v) and (uxe2x80x2, vxe2x80x2).
Based on the foregoing principle, a trajectory linking N points in an image is drawn in the xcfx81-xcex8 space, and the cross point of the trajectory is obtained in order to define a straight line fitted to the set of points in the image. This processing is referred to as the Hough transform. For obtaining the cross point, after the elements of an array expressing the xcfx81-xcex8 space are each initialized to 0, every time the trajectory (sine curve) passes through an element, a value of image data is added to the element. Finally, elements having large values are extracted. Thus, when the Hough transform is employed, a graphic of a straight line can be extracted from (that is, detected in) an image.
Assuming that image data at any point (x, y) in the original system of x and y coordinates is a(x, y), the Hough transform AH(xcfx81, xcex8) of the image data is expressed as follows:
AH(xcfx81, xcex8)=∫∫a(x, y)xc2x7xcex4(xcfx81xe2x88x92xxc2x7cos xcex8xe2x88x92yxc2x7sin xcex8)dxdyxe2x80x83xe2x80x83(1)
This expression means that a value a(x, y) is added to the sine curve expressed as xcfx81=xxc2x7cos xcex8+yxc2x7sin xcex8 in the xcfx81-xcex8 space.
A normally adopted method is such that according to the expression (1), the length xcfx81 (=xxc2x7cos xcex8+yxc2x7sin xcex8) is calculated with the x and y coordinates fixed and with the angle xcex8 varied. In the prior art, calculations of cos xcex8 and sin xcex8 are needed, and thus the number of arithmetic operations becomes increased.
The foregoing method based on the expression (1) requires a considerable number of arithmetic operations for calculating x and y coordinates of data to be added to each other. However, an essential arithmetic operation with respect to the Hough transform is addition of data a(x, y), indicated by the expression (1). The calculation of x and y coordinates is not a principal part of the Hough transform. The number of arithmetic operations required for the calculation of x and y coordinates can be further reduced by efficiently selecting data serving as an addend.
However, no known art has provided a means capable of efficiently specifying x and y coordinates that locate data serving as an addend. This poses a problem that operations needed for projecting two-dimensional data on a plurality of straight lines having different inclinations, cannot be achieved at a high speed.
An object of the present invention is to provide a data conversion processing circuit capable of carrying out the Hough transform by performing a small number of arithmetic operations and eventually contributing to an increase in processing speed.
For accomplishing the object, according to the present invention, operations are carried out with an angle xcex8 fixed so that x and y coordinates locating data serving as an addend can be produced efficiently. Moreover, for different angles xcex8, the operations are carried out in a time-division manner.
Specifically, when the aforesaid expression (1) is rewritten, the following expression is drawn out:
AH(xcfx81, xcex8)=∫a(xcfx81xc2x7cos xcex8xe2x88x92txc2x7sin xcex8, xcfx81xc2x7sin xcex8+txc2x7cos xcex8)dtxe2x80x83xe2x80x83(2)
This expression indicates that when the angle xcex8 is fixed, addition should be carried out in the direction of t perpendicular to the direction of xcfx81. As seen from this expression, once coordinates (x, y) locating data serving as an addend, that is, (xcfx81xc2x7cos xcex8xe2x88x92txc2x7sin xcex8, xcfx81xc2x7sin xcex8+txc2x7cos xcex8) can be obtained efficiently, the Hough transform can be carried out efficiently.
According to the method based on the expression (1), the operations are carried out with the x and y coordinates fixed. Input data a(x, y) should therefore be fetched once. By contrast, according to the present invention, since the operations are carried out with the angle xcex8 fixed, the same input data a(x, y) is used many times at different time instants. For improving efficiency, the input data a(x, y) should be fetched into a storage area to which access can be achieved quickly. Among the fetched data items, x and y coordinates that locate data serving as an addend are produced according to the angle xcex8, and data serving actually as an addend is selected according to the coordinate data. The selected data are summed up. This results in a Hough transform expressed in the xcfx81-xcex8 space.
For realizing the operations, a data conversion processing circuit in accordance with the present invention comprises a data storage unit in which data located by x and y coordinates is stored, a coordinate generation unit for sequentially producing x and y coordinates locating data that serves as an addend according to an angle xcex8 relative to the x axis, and generating a selection signal used to select data located by the x and y coordinates, a data selection unit for selecting data, which serves as an addend, from among data items stored in the data storage unit, and an addition unit for adding the selected data. For producing coordinates and selecting data, the Hough transform given by the expression (2) is employed.
According to the present invention, in the data conversion processing circuit, a change in coordinates (xcfx81xc2x7cos xcex8xe2x88x92txc2x7sin xcex8, xcfx81xc2x7sin xcex8+txc2x7cos xcex8), which is used to select input data a(x, y), due to a change in element t is expressed as (xcex94txc2x7sin xcex8, xcex94txc2x7cos xcex8) and substantially independent of xcfx81 and t. Consequently, the number of operations needed for producing coordinates can be reduced drastically.
Moreover, since addition of selected data items can be carried out as a parallel operation, operations involved in data conversion can be carried out at a high speed. For example, when data Nx*Ny in the system of x and y coordinates (two-dimensional data defined by Nx pixels in the x direction and Ny pixels in the y direction) is converted into corresponding data Nxcfx81*Nxcex8 in the xcfx81-xcex8 space, about Nx or Ny operations can be carried out as a parallel operation using about Nx or Ny adders.
By contrast, according to the method based on the expression (1), for achieving about Nx or Ny operations as a parallel operation, a large number of arithmetic operations or data items stored in ROMs are needed for producing coordinates. The method is therefore disadvantageous.
Discrete coordinates are used in reality. Therefore, strictly speaking, a change in coordinates (xcfx81xc2x7cos xcex8xe2x88x92txc2x7sin xcex8, xcfx81xc2x7sin xcex8+txc2x7cos xcex8), which is used to select input data a(x, y), due to a change in element t is dependent on xcfx81 and t. However, as long as the discrete coordinates are determined properly, the change will be independent of xcfx81. This is, for example, achieved as described below.
When the angle xcex8 relative to the x axis ranges from xe2x88x92xcfx80/4 to xcfx80/4, one data item is selected for each y coordinate as data serving as an addend. A change relative to the xcfx81 axis is compensated for by shifting data to be selected in the x direction. Moreover, when the angle xcex8 ranges from xe2x88x92xcfx80/2 to xe2x88x92xcfx80/4 or from xcfx80/4 to xcfx80/2, one data item is selected for each x coordinate as data serving as an addend. A change relative to the xcfx81 axis is compensated for by shifting data to be selected in the y direction. This process provides the merit described below.
To begin with, since one data item is selected for each x coordinate or y coordinate as data serving as an addend, the range of data items to be selected is narrow. The circuitries of a coordinate generation unit and data selection unit are therefore simplified. Moreover, a change relative to the xcfx81 axis can be compensated for by merely shifting data to be selected in the x or y direction. The circuitry of the coordinate generation unit can be simplified. By utilizing the fact that an absolute value of a change in y or x coordinate is 0 or 1, the circuitry of the coordinate generation unit can further be simplified. Furthermore, each input data a(x, y) is used as an addend without being duplicated or missed. Data manipulation, to be performed as subsequent processing, can be carried out easily.
The method based on the expression (2) has the demerit that the effective value of xcfx81 or t varies depending on the value of the angle xcex8. However, since this variation can be predicted, proper correction can be carried out after a Hough transform is completed. When an inverse Hough transform is carried out as described later, the variation is canceled due to the same dependency on the angle xcex8. The correction is therefore unnecessary.